let arr = [4, 10, 13, 5, 1, 2, 20, 3, 41]

function heapSort(arr, n) {
  // 堆化节点
  buildDeap(arr, n)
  let i
  for (i = n - 1; i >= 0; i--) {
    // 大顶堆， 交换顶点和最后一个节点
    swap(arr, i, 0)
    // 每次交换完成， 从i 的位置开始堆化继续，交换
    heapify(arr, i, 0)
  }
}
function buildDeap(arr, n) {
  // 获取最后一个节点
  let last_node = n - 1
  // 获取最后一个节点的父节点
  let parent = Math.floor((last_node - 1) / 2)
  let i
  for (i = parent; i >= 0; i--) {
    console.log(i)
    // 从倒数第二次开始， 最后一个子节点的父节点， 开始遍历进行堆化，
    heapify(arr, n, i)
  }
}

// 堆化
function heapify(arr, n, i) {
  if (i >= n) return
  // 找出两个子节点
  let c1 = 2 * i + 1
  let c2 = 2 * i + 2
  // 假设最大值为i
  let max = i

  // 如果c1 大于 max， 交换下标
  if (c1 < n && arr[c1] > arr[max]) {
    max = c1
  }
  // 如果c2 大于max， 交换下标
  if (c2 < n && arr[c2] > arr[max]) {
    max = c2
  }
  // 交换数组中的位置
  if (max !== i) {
    swap(arr, max, i)
    // 对max 这个分支下的节点进行堆化
    heapify(arr, n, max)
  }
}

function swap(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

heapSort(arr, arr.length)

console.log(arr)
